package Astar;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import s3t.gameControl.GameCore;
import s3t.gameControl.timer.TimerAction;



 /*
  * A* Patchfinder - Vr. 0.6
  *
  * @Author: Frederico Miller
  *
  * 
  *
  * Thanks To:
  * http://www.policyalmanac.org/games/aStarTutorial.htm
  * http://code.google.com/p/baseoneaslib/
  * http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths
  * http://www.cokeandcode.com/pathfinding
  */

public class Astar
{
      private Node mapNodes[][];
      private int[][] matrixMap;
      
      private ArrayList<Node> openList;
      private ArrayList<Node> closedList;
      private int tileWidth;
      private int tileHeight;
      private int blocked = 1;

      private final int RECT = 1;
      private final int DIAG = (int)( Math.abs( Math.sqrt( RECT * 2 ) ) );

      private final int FULL = 0;
      private final int STRAIGHT = 1;
      private final int DIAGONAL = 2;
      private boolean ENABLE_DIAG_TURN = false;


      public Astar(){}


      /*
       * Transforma matrix2d em mapa navegavel pelo A*
       *
       * @param     int[][]     Matriz com o layout do mapa
       * @param     int         Largura do mapa em pixel
       * @param     int         Offset do ponto de registro to tile
       * @param     int         Altura do mapa em pixel
       * @param     int         Numero representando paredes
       *
       */
      public void loadMap( int[][] map, int mapWidth, int mapHeight, int wall )
      {

          tileWidth = (mapWidth / map[ 0 ].length);
          tileHeight = (mapHeight / map.length);

          matrixMap = map;

          blocked = wall;

          int ROWS = map.length;
          int COLS = map[ 0 ].length;

          mapNodes = new Node[ ROWS + 1 ][ COLS + 1 ];

          for( int rows = 0; rows < ROWS; rows++ )
          {
                for( int cols = 0; cols < COLS; cols++ )
                {
                    mapNodes[ rows + 1 ][ cols + 1 ] = new Node( new Point( (cols * tileWidth) + tileWidth,
                                                                      (rows * tileHeight) + tileHeight ) );

                    if( map[ rows ][ cols ] == wall )
                    {
                         mapNodes[ rows + 1 ][ cols + 1 ].blocked = true;
                    }
                    else
                    {
                         mapNodes[ rows + 1 ][ cols + 1 ].blocked = false;
                    }
                }
           }
      }


      /*
       * Busca A*
       *
       * @param     Point               X,Y do saida
       * @param     Point               X,Y do chegada
       * @param     int                 Heuristica da busca: 0 = Euclidian, 1 = Dr.Manhathan
       * @param     int                 Tipo de busca: 0 = Completa(8 direções), 1 = Ortogonal, 2 = Diagonal
       * @param     Boolean             Bloqueia movimento diagonal nas curvas de canto para evitar problemas de colisão
       *
       * @return    ArrayList<Point>    Array de Pontos com o caminho ótimo....ou não....
       *
       */
      public ArrayList<Point> find( Point start, Point end, int heuristic, int type, Boolean diagCornerTurn )
      {

          openList = new ArrayList<Node>();
          closedList = new ArrayList<Node>();

          Boolean gotApath = false;

          ENABLE_DIAG_TURN = diagCornerTurn;

          Node startNode = getNodeOnMap( start.x, start.y ); 
          Node endNode = getNodeOnMap( end.x, end.y );

          Node currentNode = startNode;
        
          currentNode.h = distance( startNode, endNode, heuristic );

          openList.add( currentNode );

          while( !gotApath )
          {
               CostComparator comparator = new CostComparator();
               Collections.sort( openList, comparator );
               //Collections.reverse( openList );

               if( openList.size() <= 0) break;

               currentNode = openList.get( 0 );
               openList.remove( 0 );


               if( currentNode.pos.x == endNode.pos.x && currentNode.pos.y == endNode.pos.y )
	       {
                    //System.out.println( "@I got a freaking path!" );
                    gotApath = true;
                    break;
	       }

               closedList.add( currentNode );

               for( Node node : searchNodeConnections( currentNode, type ) )
	       {
                    if( !openList.contains( node ) && !closedList.contains( node ) )
		    {
                        openList.add( node );
                	node.parent = currentNode;
               		node.h = distance( node, endNode, heuristic );
			node.g = currentNode.g;
                    }
                    else 
                    {
			double fullCost = currentNode.g + node.getCost();
			if( fullCost < node.getCost() )
			{
                            node.parent = currentNode;
                            node.g = currentNode.g;
			}
                    }
		}
          }

          if( gotApath )
	  {
	      ArrayList<Point> result = new ArrayList<Point>();
              result.add( currentNode.getPos() );

              while( currentNode.parent != null )
              {
                  currentNode = currentNode.parent;
                  result.add( currentNode.getPos() );
	      }
                  Collections.reverse( result );
                  resetMap();
		  return result;
          }
          else
          {
              return new ArrayList<Point>();
          }

      }


      /*
       * 
       * Cria lista com nodes conectados
       *
       */
      private ArrayList<Node> searchNodeConnections( Node parent, int searchType )
      {
            ArrayList<Node> connectionsArray = new ArrayList<Node>();
            Node kid = null;

            int xPos = parent.pos.x;
            int yPos = parent.pos.y;
            
            for( int direction = 1; direction <= 8; direction++ )
            {
                if( searchType == STRAIGHT || searchType == FULL )
		{
                    switch( direction )
                    {
                        case 1:
                            kid = checkNodeConnections( xPos - tileWidth, yPos, direction ); break;
                        case 2:
                            kid = checkNodeConnections( xPos + tileWidth, yPos, direction ); break;
                        case 3:
                            kid = checkNodeConnections( xPos, yPos - tileHeight, direction ); break;
                        case 4:
                            kid = checkNodeConnections( xPos, yPos + tileHeight, direction ); break;
                    }
		}

                if ( searchType == DIAGONAL || searchType == FULL )
		{
                    switch( direction )
                    {
			case 5:
                            kid = checkNodeConnections( xPos - tileWidth, yPos - tileHeight, direction );
                            if( !ENABLE_DIAG_TURN && kid != null && xPos > tileWidth && yPos > tileHeight )
                            {
                                Node tempNode1 = getNodeOnMap( xPos - tileWidth, yPos );
                                Node tempNode2 = getNodeOnMap( xPos, yPos - tileHeight );
                                if ( tempNode1.blocked || tempNode2.blocked ) kid = null;
                            }
                            break;
			case 6:
                            kid = checkNodeConnections( xPos - tileWidth, yPos + tileHeight, direction );
                            if( !ENABLE_DIAG_TURN && kid != null && xPos > tileWidth && yPos < ( tileHeight * mapNodes.length ) - tileHeight )
                            {
                                Node tempNode1 = getNodeOnMap( xPos - tileWidth, yPos );
                                Node tempNode2 = getNodeOnMap( xPos, yPos + tileHeight );

                                if (  tempNode1.blocked || tempNode2.blocked ) kid = null;
                            }
                            break;
			case 7:
                            kid = checkNodeConnections( xPos + tileWidth, yPos - tileHeight, direction );
                            if( !ENABLE_DIAG_TURN && kid != null && xPos < ( tileWidth * mapNodes[ 0 ].length ) - tileWidth && yPos > tileHeight )
                            {
                                Node tempNode1 = getNodeOnMap( xPos + tileWidth, yPos );
                                Node tempNode2 = getNodeOnMap( xPos, yPos - tileHeight );

                                if ( tempNode1.blocked || tempNode2.blocked ) kid = null;
                            }
                            break;
			case 8:
                            kid = checkNodeConnections( xPos + tileWidth, yPos + tileHeight, direction );
                            if( !ENABLE_DIAG_TURN && kid != null && xPos < ( tileWidth * mapNodes[ 0 ].length ) - tileWidth && yPos < ( tileHeight * mapNodes.length ) - tileHeight)
                            {
                                Node tempNode1 = getNodeOnMap( xPos + tileWidth, yPos );
                                Node tempNode2 = getNodeOnMap( xPos, yPos + tileHeight );

                                if (  tempNode1.blocked || tempNode2.blocked ) kid = null;
                            }
                            break;
                    }
       
		}

		if( kid != null  ) connectionsArray.add(kid);
	     }

             return connectionsArray;
         }


      /*
       * 
       * Verifica conexões do node
       * 
       */
      private Node checkNodeConnections( int x, int y, int d )
      {
          if (x <= 0 || x >= ( mapNodes[ 0 ].length * tileWidth ) || y <= 0 || y >= ( mapNodes.length * tileHeight ) )
          {
              return null;
          }

          Node node = getNodeOnMap( x, y );

          int cost = ( d >= 5 ? DIAG : RECT );

          if( !node.blocked )
          {
             node.g += cost;
             return node;
          }

	  return null;
       }


      /*
       * 
       * Retorna Node da posição X(coluna),Y(linha) da matrix
       *
       */
       private Node getNodeOnMap( int x, int y )
       {
           Node node;
           node = mapNodes[ y / tileHeight ][ x / tileWidth ];

           if( node == null ) return null;

           return node;
       }


      /*
       *
       * Calcula distancia conforme heuristica
       *
       */
       private double distance( Node start, Node end, int type )
       {
           double heuristic = 0;

           switch ( type ) 
           {
               //Euclidian
               case 0:
                    int dx = end.pos.x - start.pos.x;
                    int dy = end.pos.y - start.pos.y;
                    heuristic = ( Math.sqrt( ( dx * dx ) + ( dy * dy ) ) );
               break;
               // Dr.Manhathan
               case 1:
                    heuristic = Math.abs( start.pos.x - end.pos.x ) + Math.abs( start.pos.y - end.pos.y );
               break;
           }
           
           return heuristic;
       }


      public void resetMap()
      {

          int ROWS = matrixMap.length;
          int COLS = matrixMap[ 0 ].length;
          
          mapNodes = new Node[ ROWS + 1 ][ COLS + 1 ];

          for( int rows = 0; rows < ROWS; rows++ )
          {
                for( int cols = 0; cols < COLS; cols++ )
                {
                    mapNodes[ rows + 1 ][ cols + 1 ] = new Node( new Point( (cols * tileWidth) + tileWidth,
                                                                      (rows * tileHeight) + tileHeight ) );

                    if( matrixMap[ rows ][ cols ] == blocked )
                    {
                         mapNodes[ rows + 1 ][ cols + 1 ].blocked = true;
                    }
                    else
                    {
                         mapNodes[ rows + 1 ][ cols + 1 ].blocked = false;
                    }
                }
           }
      }



  
}
